package com.hle;

public class BloomFilter<T> {

	private int bitSize;
	private long[] bits;
	private int hashSize;

	public BloomFilter(int n ,double p) {
		if (n <= 0 || p <=0 || p >= 1) {
			throw new IllegalArgumentException("wrong n or p");
		}
		double ln2 = Math.log(2);
		bitSize = (int) (- (n * Math.log(p)) / (ln2 * ln2));
		hashSize = (int) (bitSize * ln2 / n);
		bits = new long[(bitSize + Long.SIZE - 1) / Long.SIZE];
	}

	public boolean put(T value) {
		nullCheck(value);
		// 利用value生成2个整数
		int hash1 = value.hashCode();
		int hash2 = hash1 >>> 16;

		boolean result = false;
		for (int i = 1; i <= hashSize; i++) {
			int combinedHash = hash1 + (i * hash2);
			if (combinedHash < 0) {
				combinedHash = ~combinedHash;
			} 
			// 生成一个二进位的索引
			int index = combinedHash % bitSize;
			// 设置index位置的二进位为1
			if (set(index)) result = true;

			//   101010101010010101
			// | 000000000000000100   1 << index
			//   101010111010010101
		}
		return result;
	}

	public boolean contains(T value) {
		nullCheck(value);
		// 利用value生成2个整数
		int hash1 = value.hashCode();
		int hash2 = hash1 >>> 16;
	
		for (int i = 1; i <= hashSize; i++) {
			int combinedHash = hash1 + (i * hash2);
			if (combinedHash < 0) {
				combinedHash = ~combinedHash;
			} 
			// 生成一个二进位的索引
			int index = combinedHash % bitSize;
			// 查询index位置的二进位是否为0
			if (!get(index)) return false;
		}
		return true;
	}
	
	private boolean set(int index) {
		long value = bits[index / Long.SIZE];
		int bitValue = 1 << (index % Long.SIZE);
		bits[index / Long.SIZE] = value | bitValue;
		return (value & bitValue) == 0;
	}
	
	private boolean get(int index) {
		long value = bits[index / Long.SIZE];
		int bitValue = 1 << (index % Long.SIZE);
		return (value & bitValue) != 0;
	}
	
	private void nullCheck(T value) {
		if (value == null) {
			throw new IllegalArgumentException("Value must not be null.");
		}
	}
}
